package main

import (
	"fmt"
	"strconv"
)

func permuteUnique(nums []int) [][]int {
	vis := make([]bool, len(nums))
	result := make([]int, 0)
	retM := make(map[string]struct{})
	ret := make([][]int, 0)
	var backTrace func(n int, vis []bool, result []int)
	var transferSliceToString func([]int) string

	transferSliceToString = func(ints []int) string {
		ret := ""
		for i := 0; i < len(ints); i++ {
			ret += strconv.Itoa(ints[i]) + ","
		}

		return ret
	}

	backTrace = func(n int, vis []bool, result []int) {
		if len(vis) == n {
			str := transferSliceToString(result)
			_, ok := retM[str]
			if ok {
				return
			}
			retM[str] = struct{}{}

			temp := make([]int, len(result))
			for i := 0; i < len(result); i++ {
				temp[i] = result[i]
			}

			ret = append(ret, temp)
			return
		}

		for i := 0; i < len(vis); i++ {
			if !(vis[i]) {
				vis[i] = true
				result = append(result, nums[i])
				backTrace(n+1, vis, result)
				vis[i] = false
				result = result[:len(result)-1]
			}
		}
	}

	backTrace(0, vis, result)

	return ret
}

func main() {
	fmt.Println(permuteUnique([]int{1, 1, 2}))

}
